#pragma once

#include <algorithm>
#include <string>
#include <tuple>
#include <utility>

namespace solution_838
{

class Solution
{
public:
    std::string pushDominoes(std::string dominoes)
    {
        if (dominoes.empty())
            return dominoes;
        auto [l, r] = findDotInterval(dominoes, 0);
        while (r < dominoes.size()) {
            pushAll(dominoes, l, r);
            std::tie(l, r) = findDotInterval(dominoes, r + 1);
        }
        return dominoes;
    }

private:
    std::pair<int, int> findDotInterval(std::string& dominoes, int first) {
        int left = dominoes.size();
        for (; first < dominoes.size(); ++first) {
            if (dominoes.at(first) == '.') {
                left = first;
                break;
            }
        }
        int right = left;
        for (; right < dominoes.size(); ++right) {
            if (right + 1 == dominoes.size() || dominoes.at(right + 1) != '.')
                break;
        }
        return { left, right };
    }

    void pushAll(std::string& dominoes, int l, int r) {
        auto first = dominoes.begin() + l;
        auto last = dominoes.begin() + r + 1;
        if (l == 0) {
            if (r + 1 < dominoes.size() && dominoes.at(r + 1) == 'L')
                std::fill(first, last, 'L');
        } else if (r + 1 == dominoes.size()) {
            /* left > 0 */
            if (dominoes.at(l - 1) == 'R')
                std::fill(first, last, 'R');
        } else {
            if (dominoes.at(l - 1) == 'R' && dominoes.at(r + 1) == 'L') {
                int len = r - l + 1;
                std::fill(first, first + len / 2, 'R');
                std::fill(first + (len + 1) / 2, last, 'L');
            } else if (dominoes.at(l - 1) == 'R') {
                std::fill(first, last, 'R');
            } else if (dominoes.at(r + 1) == 'L') {
                std::fill(first, last, 'L');
            }
        }
    }
};

}  /* namespace solution_838 */
